# -*- coding: utf-8 -*-

'''

@author: wyndem
@Emil:   wyndem.wen@timevary.com
@FileName: test.py
@Time: 2018/6/27 11:33
@Description: 

'''

#每个node只能比一次
processed=[]
#所有的邻居散列表
graph=dict()

start={}
start['a']=5
start['b']=2

graph['start']=start

a={'c':4,'d':2}
graph['a']=a

b={'a':8,'d':7}
graph['b']=b

c={'d':6,'fin':3}
graph['c']=c

d={'fin':1}
graph['d']=d

#终点
graph['fin']={}

#开销表
costs={}
costs['a']=5
costs['b']=2
costs['c']=999
costs['d']=999
costs['fin']=999

#父表
parents={}


#找出相邻的两边最小值
def find_lowest_cost_node(costs):
    lowest_cost_Min=float('inf')
    const_node=None
    for node in costs:
        cost=costs[node]
        if cost < lowest_cost_Min and node not in processed:
            lowest_cost_Min=cost
            const_node=node
    return const_node





def find_lowest_ykstl():
   node=find_lowest_cost_node(costs)

   while node is not None:
       cost=costs[node]
       neighbors=graph[node]
       for n in neighbors:
           new_cost=cost+neighbors[n]
           if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node

       processed.append(node)
       node = find_lowest_cost_node(costs)


if __name__ == '__main__':
    find_lowest_ykstl()
    print(costs)
